package com.LeeCode;

/**
 * 任意子数组和的绝对值的最大值
 */

public class Code1749 {
    public static void main(String[] args) {
        int[] nums = {1, 2, -2, 3};
        System.out.println(new Code1749().maxAbsoluteSum1(nums));
    }

    public int maxAbsoluteSum(int[] nums) {
        // 计算最大子数组和
        int maxEndingHere = 0;
        int maxSoFar = 0;

        for (int num : nums) {
            maxEndingHere = Math.max(num, maxEndingHere + num);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        // 计算最小子数组和
        int minEndingHere = 0;
        int minSoFar = 0;

        for (int num : nums) {
            minEndingHere = Math.min(num, minEndingHere + num);
            minSoFar = Math.min(minSoFar, minEndingHere);
        }

        // 返回绝对值的最大值
        return Math.max(maxSoFar, -minSoFar);
    }

    public int maxAbsoluteSum1(int[] nums) {
        int sum = 0, maxVal = 0, minVal = 0;

        for (int num : nums) {
            sum += num;
            if (sum > maxVal) maxVal = sum;
            else if (sum < minVal) minVal = sum;
        }

        return maxVal - minVal;
    }
}
